The present invention relates to an arithmetic circuit responsive to an overflow caused in consecutive addition or subtraction operation in digital signal or similar processing.
Digital signal processing is a technique to accomplish, in digital fashion, required filtering or similar processing for an input analog signal through analog-to-digital conversion. For details of such a technique, reference is made to Theory and Application of Digital Signal Processing, by Lawrence R. Rabiner et al. published in 1975 by Prentice-Hall, Inc., pp. 309-329 (Reference 1). The operation of a digital filter for use in such processing will be briefly described hereunder.
Generally, an analog filter of higher order may be replaced by a digital filter of the same order. To design such a digital filter without using such an analog filter of the same order, however, high coefficient accuracy is required for stable filtering operation. For this reason, such a filter is usually achieved by connecting second-order recursive digital filter in either cascade or parallel form. These second-order digital filters can be represented by the following equation: EQU w.sub.k =x.sub.k +.beta..sub.1 w.sub.k-1 +.beta..sub.2 w.sub.k-2 EQU y.sub.k =w.sub.k +.alpha..sub.1 w.sub.k-1 +.alpha..sub.2 w.sub.k-2 ( 1)
where x.sub.k, y.sub.k, and w.sub.k are an input signal sample value, an output signal sample value, and an internal state variable, respectively, at time k, and .alpha..sub.1, .alpha..sub.2, .beta..sub.1 and .beta..sub.2 are fixed coefficients determined by the frequency characteristics of the filter.
Alternatively, a stably operable non-recursive digital filter of higher order can be achieved without using the second-order digital filters by computing ##EQU1## by the use of the finite sample value sequence [C.sub.i .vertline.0.ltoreq.i.ltoreq.N] of impulse responses of an analog filter having corresponding characteristics.
For digital computation of equations (1) and (2), it is usual to use a simple arithmetic circuit of small hardware dimensions, in which two's complement-fixed point representation is employed for variable data such as x.sub.i and y.sub.i. For details of the two's complement representation, reference is made to Computer Science, by Alfonso F. Cardenas et al. published in 1972 by John Wiley Sons, Inc., pp. 60-66 (Reference 2). For an efficient use of the word length for expressing the variables for said operations defined by equations (1) and (2), it is possible to set a dynamic range of the variables at (-1, +1), which means that the maximum and minimum values assumed by the use of a given word length correspond to +1 and -1, respectively. For instance, if each variable has a word length of four bits, the minimum value "1000" corresponds to -1 and the maximum value "0111" to +1-2.sup. -3, which is close to +1. Thus, it can be understood that, by this notation, the most significant bit (MSB) represents the sign bit and the decimal point is located between the sign bit and the immediately following bit.
On the other hand, the above-mentioned coefficients must be so determined in designing said recursive or nonrecursive digital filter that the average level of the data-representing signal, which appears in each of the left-hand members of equations (1) and (2), may be contained within a dynamic range of (-1, +1).
Some overflow problems in the consecutive addition operation arise when such digital filters described above are achieved in hardware.
Let it be assumed that each term of the right-hand members in equations (1) and (2) comes within a predetermined range of (-1, +1). However, for instance, .beta..sub.1 w.sub.k-1 in equation (1) is not necessarily within this range because there can be the case of 1.ltoreq..beta..sub.1 &lt;2. In this case, the above-stated requirement can be satisfied by transforming the term into ##EQU2## rendering each of the coefficients less than 1. Even with this transformation, however, a first problem is that even if said digital filter is designed so that the average level of said signal of each left-hand member in equations (1) and (2) is contained within the range of (-1, +1), such level may momentarily exceed the range. If the number of terms in each right-hand member is N, the value of the corresponding left-hand term may become N times greater than the normal dynamic range. Therefore, by the above-stated representation of the variables in which only the sign bit is present above the decimal point, a momentary overflow in the operation may occur. Unless an interim result of the operation is corrected to the maximum value on either the positive or the negative side depending on whether the overflow has arisen on the positive (plus) or the negative (minus) side, an error nearly equal to the full dynamic range (an error of about 2) will occur. Such correction, in response to the overflow, is indispensable to the operation of the digital filter defined by equation (1). If a large error occurs for the internal variable w.sub.k, which is calculated based on the internal variables w.sub.k-k and w.sub.k-2, a comparatively large error will also occur for the following internal variable w.sub.k+1. Thus, subsequent internal variables will continue to store errors permanently, resulting in an unstable filtering operation. In the case of equation (2), on the other hand, since the internal variables are not affected by the overflow, there is little direct effect of the overflow even if it is not compensated for. Although this type of filter is often used for the case where a correlation is taken, a control system responsive to the extent of said correlation will be seriously affected, if the correlation substantially deviates from what it should be.
The second problem is caused due to the overflow that may occur in the course of the calculation of the right-hand members in equations (1) and (2). For instance, if an overflow occurs on the positive side in the course of the calculation, the overflow may be immediately compensated for, but in many instances it may be unnecessary to perform such overflow compensation. More particularly, each data signal is selected so that the average level of each signal of the left-hand members may lie within the proper dynamic range (-1, +1). For this reason, there will be a sufficiently high probability that for each overflow in the positive direction, an overflow will arise on the negative side to eventually hold the level within said range. Thus, even though a number of overflows may actually occur, the positive and negative overflows will offset one another in the course of the operation and the ultimate result will be free from overflow error.
To achieve such digital filtering or similar processing, a prior art arithmetic circuit employs only one adder as illustrated in FIG. 2-1, page 2-1 of MCS-85 User's Manual, published in 1978, by Intel Corporation (Reference 3). The FLAG FLIP-FLOPS, ARITHMETIC LOGIC UNIT, TEMP. REG. AND ACCUMULATOR shown in FIG. 2-1 of reference 3 constitute the arithmetic circuit. In such an arithmetic circuit, the above-mentioned overflow is dealth with by the following two methods.
The first is to shift the decimal point to a lower position. In the case of N consecutive additions, for example, the decimal point is shifted to the location between the log.sub.2 N -th bit and the ( log.sub.2 N +1)-th bit from the MSB, where the symbol indicates a Gaussian notation, which means that a value written within this symbol becomes an integer closest to the value by counting its decimal fraction as one. According to this method, even if an overflow occurs so that the dynamic range (-1, +1) is surpassed as discussed with respect to said first problem, the adder used in the arithmetic unit will never cause the overflow. This is because only data up to at most the log.sub.2 N -th bit above the decimal point is generated. Whether or not the result of the consecutive additions has overrun the proper dynamic range (-1, +1) can be judged by examining whether or not every bit above the decimal point is identical with the MSB. If any signal is found beyond said dynamic range, the overflow can be compensated for as described above.
This method is also effective to cope with said second problem. Since it serves to expand the dynamic range of the arithmetic unit, values not smaller than +1 or not greater than -1 can be maintained within one arithmetic register, even if any interim result of the operation exceeds the dynamic range of (-1, +1). Consequently, if any result of the operation is within said range of (-1, +1), it can be decided that said result has been calculated without error. Also, even if the overflow occurred in any interim result, the final result will be judged free from the overflow by said first method.
A disadvantage, however, is that this method cannot fully utilize a given word length. For instance, when eight consecutive additions are accomplished by an arithmetic circuit capable of processing data of 16 bits in word length, the decimal point is shifted to the third (i.e., log.sub.2 8=3(rd)) bit from the MSB. It follows consequently that the four most significant bits out of the 16-bit word length are used merely for the detection of overflow as well as the compensation therefor, or, in other words, the 16-bit word length processing unit is actually employed as a 12-bit word length unit.
The second method is to correct the result of the operation every time the overflow occurs, even in the course of the consecutive addition (CA) operation, to the maximum permitted value in the direction of the occurrence of the overflow (the positive or negative side). By this method, any error that may occur in the event of overflow will be smaller than in the case where the overflow is not compensated for. Therefore, the second method is efficient to prevent the unstable operation of a second-order digital filter even if the overflow occurs in the calculation of the internal state w.sub.k in equation (1). For further details of this stabilized digital filter, reference is made to a paper by Stanley L. Freeny, entitled "Special-Purpose Hardware for Digital Signal Processing", PROCEEDINGS OF THE IEEE, April issue, 1975, pp. 633-648 (Reference 4).
The second method, however, necessitates the checking of overflow upon every addition. Moreover, if applied to equation (2), which is used for the non-recursive digital filter or correlation calculation, a correction error will be accumulated every time the overflow occurs in the course of the CA operation. For this reason, the result of the operation must be corrected to the maximum value in response to the overflow. This corrected result of the CA operation, even though it is within said dynamic range (-1, +1), may consequently contain a large error component if the value of N is large.
The detection of any overflow that arises in a single addition can be carried out by either of the following two checking methods:
(1) The sign bits of the two data are checked before the addition to determine whether they are identical as well as whether the sign bit of the output data is different from them (see page 636 of Reference 4);
(2) The carry signal input to the MSB (i.e., the sign bit in this instance where two's complement representation is used) is checked to determine whether it has a different sign from the carry signal output. For details of this method (2), reference is made to The Am2900 Family Data Book with Related Support Circuits, published in 1976 by Advanced Micro Devices, Inc., p. 11 (Reference 5).